#include<iostream>
using namespace std;
#include<vector>
#include<string>
class Solution {
public:
    vector<vector<int>> dp;
    int n;
    vector<vector<string>> ans;
    vector<string> path;
    void dfs(string& s, int start) {
        if (start >= n) {
            ans.push_back(path);
            return;
        }
        for (int i = start; i < n; ++i) {
            if (dp[start][i]) {
                path.push_back(s.substr(start, i - start + 1));
                dfs(s, i + 1);
                path.pop_back();
            }
        }
        return;
    }
    vector<vector<string>> partition(string& s) {
        n = s.size();
        dp.resize(n, vector<int>(n));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (i == j || j == i + 1)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }
        dfs(s, 0);
        return ans;
    }
};